package com.example.spring.arithmetic.heap;

import java.util.Scanner;

/**
 * @author: orange
 * @create: 2023-08-07 13:26
 * @description: 小根堆
 */
public class ArraySmallHeap {
    public static void main(String[] args) {
        int[] temp = {40, 2, 33, 26, 35, 8, 8, 26, 29, 2};
        heap = new int[temp.length];
        for (int j : temp) {
            push(j);
        }
        for (int i = 0; i < temp.length; i++) {
            System.out.format("%d ", pop());
        }
    }


    private static int[] heap;

    private static int size;

    private static void down(int k) {
        int t = k;
        int l = k << 1, r = (k << 1) + 1;
        if (l <= size && heap[t] > heap[l]) {
            t = l;
        }

        if (r <= size && heap[t] > heap[r]) {
            t = r;
        }

        if (t != k) {
            int temp = heap[k];
            heap[k] = heap[t];
            heap[t] = temp;
            down(t);
        }
    }

    private static void up(int k) {
        int u = k / 2;
        if (u >= 1 && heap[k] < heap[u]) {
            int temp = heap[k];
            heap[k] = heap[u];
            heap[u] = temp;
            up(u);
        }
    }

    public static void push(int v) {
        heap[++size] = v;
        up(size);
    }

    public static int pop() {
        int v = heap[1];
        heap[1] = heap[size--];
        down(1);
        return v;
    }
}
